#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, k, r, x[500005], y[500005], s[500005], t[500005], fa[500005], w[10][10];

int get_fa(int i) {
	if (i == fa[i]) return i;
	return fa[i] = get_fa(fa[i]);
}

int solve(int a, int b) {
	for (int i = 1; i <= n; ++i) {
		fa[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		if (i != a && i != b) {
			fa[get_fa(x[i])] = get_fa(y[i]);
		}
	}
	map<int, int> mp; int fcnt = 0;
	for (int i = 1; i <= n; ++i) {
		if (!mp[get_fa(i)]) {
			mp[get_fa(i)] = ++fcnt;
		} 
	}
	memset(w, 63, sizeof(w));
	for (int i = 1; i <= m; ++i) {
		if (mp[get_fa(x[i])] != mp[get_fa(y[i])]) {
			w[mp[get_fa(x[i])]][mp[get_fa(y[i])]] = 1;
			w[mp[get_fa(y[i])]][mp[get_fa(x[i])]] = 1;
		}
	}
	for (int i = 1; i <= fcnt; ++i) w[i][i] = 0;
	for (int k = 1; k <= fcnt; ++k) {
		for (int i = 1; i <= fcnt; ++i) {
			for (int j = 1; j <= fcnt; ++j) {
				w[i][j] = min(w[i][j], w[i][k] + w[k][j]);
			}
		}
	}
	int sum = 0;
	for (int i = 1; i <= k; ++i) {
		sum += w[mp[get_fa(s[i])]][mp[get_fa(t[i])]];

	}
	return sum;
}

signed main() {
	freopen("hide.in", "r", stdin);
	freopen("hide.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k >> r;
	for (int i = 1; i <= m; ++i) cin >> x[i] >> y[i];
	for (int i = 1; i <= k; ++i) cin >> s[i] >> t[i];
	if (r == 1) {
		if (n > 5000) return 0;
		int ans = 0;
		for (int i = 1; i <= m; ++i) {
			ans = max(ans, solve(i, -1));
		}
		cout << ans << "\n";
	} else {
		if (n > 500) return 0;
		int ans = 0;
		for (int i = 1; i <= m; ++i) {
			for (int j = i; j <= m; ++j) {
				ans = max(ans, solve(i, j));
			}
		}
		cout << ans << "\n";
	}
	return 0;
}
